/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package practice.v2;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:HeapSort.java v1.0 2018/8/15 下午1:02 LvJing Exp $
 */
public class HeapSort {

    /**
     * 堆排序：也是选择类型的排序，为什么是选择？因为每趟都是选出最大的数，然后交换放在最后面，与简单选择排序类似，只不过它不是通过一一比较选择
     * 出最大的数，而是用堆的特性来做的筛选。
     */
    public void heapSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1)
            return;
        // 每一趟，选出当前范围最大数
        for (int lastPos = arr.length - 1; lastPos > 0; lastPos--) {
            buildMaxHeap(arr, lastPos);
            swap(arr, 0, lastPos);
        }
    }

    private void buildMaxHeap(int[] arr, int lastPos) {
        for (int i = (lastPos - 1)/2; i >= 0; i--) {
            int currentPos = i;
            // 存在左节点
            while (currentPos * 2 + 1 <= lastPos) {
                int biggerPos = currentPos * 2 + 1;
                // 存在右节点
                if (biggerPos < lastPos && arr[biggerPos] < arr[biggerPos+1])
                    biggerPos++;

                if (arr[currentPos] < arr[biggerPos]) {
                    swap(arr, currentPos, biggerPos);
                    currentPos = biggerPos;
                } else {
                    break;
                }
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test01() {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++)
            arr[i] = random.nextInt(100);
        System.out.println(Arrays.toString(arr));
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
